package de.uv.kilter.core.implementation;

import java.util.HashMap;
import java.util.List;
import java.util.Vector;

import de.uv.kilter.core.IConnection;
import de.uv.kilter.core.ICore;
import de.uv.kilter.core.IIterationCompletedListener;
import de.uv.kilter.core.INode;
import de.uv.kilter.exception.InfiniteLoopException;
import de.uv.kilter.exception.InvalidDataException;
import de.uv.kilter.exception.NotInitializedException;


public class Core implements ICore {

	
	private List<IIterationCompletedListener> listeners = null;
	
	private List<INode> nodes = null;
	private List<IConnection> connections = null;
	
	private List<INode> visitedSoFar = null;
	
	private boolean initialized = false;
	private int currentLoopLevel = 0;
	private final int maxLoopLevel = 5;
	
	private INode compensationNode = null;
	
	private HashMap<INode, Integer> lastCapacities = null;
	
	/**
	 * This method determines if a compensation Node is necessary and if this is the case it creates one.
	 * It uses the nodes class variable. 
	 * 
	 * Note: This method does not add the compensation Node to the nodes class variable by itself.
	 * 
	 * @return the Node if a compensation Node is necessary, null if not
	 */
	protected INode addCompensationNode() {
		INode compensationNode = null;
		int totalCapacity = 0;
		if (this.nodes != null) {
			for (INode node: this.nodes) {
				totalCapacity = totalCapacity + node.getCapacity();
			}
			
			int maxCost = 0;
			int i = 0;
			for (IConnection connection: connections) {
				i++;
				maxCost = Math.max(maxCost, connection.getCost());
			}
			
			maxCost = maxCost * i;
			
			if (totalCapacity < 0) {
				totalCapacity = totalCapacity * -1;
				// create CompensationNode
				compensationNode = new Node("Compensation Node", totalCapacity);
				compensationNode.setId(-1);
				// add connection from CompensationNode to every Node
				for (INode node: this.nodes) {
					if (node.getCapacity() < 0){
						IConnection connection = new Connection(maxCost, 0, Integer.MAX_VALUE, compensationNode, node);
						connection.setId(-1);
						connections.add(connection);
					}
					if (node.getCapacity() > 0){
						IConnection connection = new Connection(maxCost,0, Integer.MAX_VALUE, node, compensationNode);
						connection.setId(-1);
						connections.add(connection);
					}
				}
				nodes.add(compensationNode);
			} else if (totalCapacity > 0) {
				totalCapacity = totalCapacity * -1;
				// create CompensationNode
				compensationNode = new Node("Compensation Node", totalCapacity);
				compensationNode.setId(-1);
				// add connection from every Node to CompensationNode
				for (INode node: this.nodes) {
					if (node.getCapacity() > 0){
						IConnection connection = new Connection(maxCost, 0, Integer.MAX_VALUE, compensationNode, node);
						connection.setId(-1);
						connections.add(connection);
					}
					if (node.getCapacity() < 0){
						IConnection connection = new Connection(maxCost, 0, Integer.MAX_VALUE, node, compensationNode);
						connection.setId(-1);
						connections.add(connection);
					}
				}
				nodes.add(compensationNode);
			}
		}
		return compensationNode;
	}

	/**
	 * @see ICore#addIterationCompletedListener(IIterationCompletedListener)
	 */
	@Override
	public void addIterationCompletedListener(
			IIterationCompletedListener listener) {
		if (listeners == null)
			listeners = new Vector<IIterationCompletedListener>();
		
		listeners.add(listener);
	}

	/**
	 * This method calculates the maximum available capacity over the whole connection from Node A to Node B.
	 * It also adds phantom connections using the calculated capacity.
	 * 
	 * @param connections the connection from Node A to Node B as List, may be null
	 */
	protected void calculateCapacityAndCreatePhantomConnections(List<IConnection> connections)
	{
		if (connections != null) {
			int maxValue = Integer.MAX_VALUE; // so that the first value found is most likely smaller
			for (IConnection connection: connections)
			{
				maxValue = Math.min(maxValue, getFreeCapacityOnConnection(connection)); //lower value found
			}
			
			// lowest capacity on the connections found, can now create/modify phantom connections
			for (IConnection connection: connections) {
				if (connection instanceof PhantomConnection) {
					// PhantomConnection used, so reduce its own capacity
					connection.setMaximumCapacity(connection.getMaximumCapacity()- maxValue);
				} else {
					IConnection phantomConnection = connection.getSourceNode().getInboundingPhantomConnectionForGivenSourceNode(connection.getTargetNode());
					// check for existing phantom Node
					if (phantomConnection != null)
						// PhantomConnection exists, so increase its capacity
						phantomConnection.setMaximumCapacity(phantomConnection.getMaximumCapacity() + maxValue);
					// No PhantomConnection found, so create a new one
					else new PhantomConnection(	
							connection.getCost(), 
							maxValue,
							connection.getTargetNode(),
							connection.getSourceNode());
				}
			}	
		}
	}

	/**
	 * @see ICore#compute()
	 */
	@Override
	public void compute() throws NotInitializedException, InvalidDataException, InfiniteLoopException {
		
		if (!initialized)
			throw new NotInitializedException("Compute() may not be called before initialize()");
		
		
		try {
			prepareForKilter();
			
			outOfKilter();
			fireIterationCompleted(null, null);
			initialized = false;
		}catch(NotInitializedException nie) {
			throw nie;
		}catch(InvalidDataException ide) {
			throw ide;
		} catch (InfiniteLoopException ile) {
			throw ile;
		}finally {
			initialized = false;
		}
	}

	/**
	 * This method computes the maximal flow between a SourceNode and a TargetNode.
	 * 
	 * @param source the SourceNode
	 * @param target the TargetNode
	 * @return a List of PhantomConnections, that reflect the path of the maximum flow
	 * 			between the Source and TargetNode. Attention: The real flow is vice versa.
	 */
	protected List<IConnection> computeMaximalFlow(INode source, INode target)
	{
		List<List<IConnection>> allPathes = new Vector<List<IConnection>>();
		List<IConnection> currentPath = null;
		currentPath = getPath(source, target);
		while (currentPath != null) {
			allPathes.add(currentPath);
			calculateCapacityAndCreatePhantomConnections(currentPath);
			currentPath = getPath(source, target);
			
		}
		
		List<IConnection> phantomConnections = new Vector<IConnection>();
		for (List<IConnection> path: allPathes) {
			if (path != null)
				for (IConnection connection: path) {
					IConnection phantomConnection = connection.getSourceNode().getInboundingPhantomConnectionForGivenSourceNode(connection.getTargetNode());
					if (phantomConnection != null && !phantomConnections.contains(phantomConnection)) phantomConnections.add(phantomConnection);
				}
		}
		// Should not be removed at this point...
//		removePhantomConnectionsFromAllNodes();
		return phantomConnections;
	}
	
	/**
	 * This method will create identical copies of the underlying data. 
	 * Afterwards it will call the {@link IIterationCompletedListener#iterationCompleted(List, List)}
	 * of any registered listener.
	 * 
	 * @param nodes - the internal nodes list
	 * @param connections - the internal connections list
	 */
	private void fireIterationCompleted(List<INode> nodes, List<IConnection> connections) {
		if (listeners != null) {
			List<INode> copiedNodes = null;
			List<IConnection> copiedConnections = null;
			
			
			if (nodes != null && connections != null) {
				copiedNodes = new Vector<INode>();
				copiedConnections = new Vector<IConnection>();
				HashMap<INode, INode> originalAndCopiedNodes = new HashMap<INode, INode>();
				
				for(INode node: nodes) {
					INode copiedNode = node.getCopyWithoutConnections();
					originalAndCopiedNodes.put(node, copiedNode);
					copiedNodes.add(copiedNode);
				}
				
				for(IConnection connection: connections) {
					IConnection copiedConnection = new Connection();
					
					copiedConnection.setCost(connection.getCost());
					copiedConnection.setDecreasedCost(connection.getDecreasedCost());
					copiedConnection.setId(connection.getId());
					copiedConnection.setLoad(connection.getLoad());
					copiedConnection.setMaximumCapacity(connection.getMaximumCapacity());
					copiedConnection.setMinimumCapacity(connection.getMinimumCapacity());
					copiedConnection.setName(connection.getName());
					copiedConnection.setState(connection.getState());
					
					INode copiedSourceNode = originalAndCopiedNodes.get(connection.getSourceNode());
					INode copiedTargetNode = originalAndCopiedNodes.get(connection.getTargetNode());
					
					copiedConnection.setSourceNode(copiedSourceNode);
					copiedConnection.setTargetNode(copiedTargetNode);
//					copiedSourceNode.addOutboundingConnection(copiedConnection);
//					copiedTargetNode.addInboundingConnection(copiedConnection);
					
					copiedConnections.add(copiedConnection);
				}
				
				if (this.compensationNode != null) {
					INode copiedCompensationNode = originalAndCopiedNodes.get(this.compensationNode);
					if (copiedCompensationNode.getOutboundingConnections() != null)
						for (IConnection connection: copiedCompensationNode.getOutboundingConnections())
							connection.getTargetNode().addCapacity(-connection.getLoad());
					
					if (copiedCompensationNode.getInboundingConnections() != null)
						for (IConnection connection: copiedCompensationNode.getInboundingConnections())
							connection.getSourceNode().addCapacity(connection.getLoad());
				}
			}
			
			for (IIterationCompletedListener listener: listeners)
				listener.iterationCompleted(copiedNodes, copiedConnections);
		}
		
		
	}
		

	
	/**
	 * This method calculates the free capacity of a connection (maxCapacity - currentCapacity).
	 * It regards phantom connections, too.
	 * 
	 * @param connection the connection used to calculate the capacity; may be null
	 * @return the free capacity of the connection (0 if there is none)
	 */
	private int getFreeCapacityOnConnection(IConnection connection) {
		int freeCapacity = 0;
		if (connection != null) {
			freeCapacity = connection.getMaximumCapacity() - connection.getLoad();
			// Check for phantom connection
			IConnection phantomConnection = connection.getSourceNode().getInboundingPhantomConnectionForGivenSourceNode(connection.getTargetNode());
			if (phantomConnection != null) { //phantom connection found
				freeCapacity = freeCapacity - phantomConnection.getMaximumCapacity();
			}
		}
		return freeCapacity;
	}
	
	/**
	 * This method is invoked to compute any child with a negative capacity. This method is used
	 * to create the initial balance between all nodes.
	 * 
	 * @param parent - the node, whose child needs to have a negative capacity
	 * @return the path to the node
	 */
	protected List<IConnection> getNegativeChild(INode parent)
	{
		List<IConnection> tmp = null;
		for (INode node: nodes)
			if (node.getCapacity() < 0)
			{
				tmp = getPath(parent, node, false);
				if (tmp != null)
					return tmp;
			}
		return null;
	}
	
	/**
	 * This method computes any possible semicycle from <b>source</b> to <b>target</b>
	 * by recursively invoking itself. 
	 * 
	 * @param goneSoFar - the path that has already been gone
	 * @param source - the sourcenode
	 * @param target - the targetnode
	 * @return the path from source to target
	 */
	protected List<INode> getSemiCylce(List<INode> goneSoFar, INode source, INode target)
	{
		/*
		 * The first time the getSemiCycle method is called (if goneSoFar has the
		 * size 0) the starting values are added to the goneSoFar and visitedSoFar
		 * array. The visitedSoFar Array correlates to the marking process of the
		 * out-of-kilter algorithm and is only used if no semi cycle was found.
		 */
		if (goneSoFar.size()==0) {
			goneSoFar.add(target);
			goneSoFar.add(source);
			visitedSoFar = new Vector<INode>();
			// Only the source node may be added here, as the target node is not marked at this point of the algortithm
//			visitedSoFar.add(target);
//			visitedSoFar.add(source);
		}
		
		boolean visited = false;
		if (visitedSoFar != null)
			for (INode visitedNode: visitedSoFar) {
				if (visitedNode == source)
					visited = true;
			}
		if (!visited && source != null)
			visitedSoFar.add(source);
		
//		if (!visitedSoFar.contains(source));
//			visitedSoFar.add(source);
		
		// The "markable" nodes are the nodes that can be used in the semi cycle
		List<INode> markables = source.getMarkableNodes();
		// If there are no markables we can do nothing at this point, we can only go back,
		// or if we just started, fail
		if (markables != null) 
		{ 
			for (INode node: markables)
			{					
					if (node == target)
					{
						// If goneSoFar is smaller than three, we're trying to go back from where we came
						if (goneSoFar.size() > 2)
						{
							goneSoFar.add(node);
							return goneSoFar; // we've found a semi cycle and can stop here
						}
					}
					else
					{
						// we don't need to mark here, as we will call the getSemiCycle that'll mark the node
//						if (!visitedSoFar.contains(node))
//							visitedSoFar.add(node);
						
						// if next node has not been visited so far
						if (!goneSoFar.contains(node))
						{
							goneSoFar.add(node); // We remember the path we used to get here, so that we don't go back
							
							// Here we start a new recursive step with the path already gone, the current "markable" node and the target
							List<INode> nodes = getSemiCylce(goneSoFar, node, target);
							// If nodes does not equal null we've found a path in a deeper recursive step and hand the result to the top
							if (nodes != null) 
								return nodes;
							// The next node had no "markable" connection or was a blind end, so we had to go back
							goneSoFar.remove(node);
						}		
						// No return here!!! The Connection has to check all its "markable" connections...
					}
				}
			}
		// If there are no markable connections or all connections were blind ends, 
		// the reason is that this node doesn't help us finding a semi cycle, so we can return null here
		return null;	
	}
	
	/**
	 * This method returns one random path between the sourceNode and
	 * the targetNode. The method itself will invoke
	 * {@link Core#getSubPath(List, INode, INode)}.
	 * 
	 * @param source the start node
	 * @param target the sink node
	 * @see Core#getSubPath(List, INode, INode)}
	 * @return the list of connections which define the path between the 
	 * nodes, which may be null, if no path is possible
	 */
	protected List<IConnection> getPath(INode source, INode target, boolean checkForCapacity)
	{
		return getSubPath(new Vector<IConnection>(), source, target, checkForCapacity);
	}
	
	/**
	 * @see #getPath(INode, INode, true)}
	 */
	protected List<IConnection> getPath(INode source, INode target)
	{
		return getSubPath(new Vector<IConnection>(), source, target, true);
	}
	
	/**
	 * This method will recursively invoke itself to find out a possible path
	 * between the given sourceNode and the given targetNode. As long as 
	 * sourceNode and targetNode have no direct connection, the method will 
	 * enter another level of recursion. 
	 * To avoid circular movements through a network of connections, the 
	 * method will keep a list of visited connections and carry it through
	 * every level of recursion. Once the final way from source to target
	 * has been found, the method returns this path.
	 * 
	 * @param goneSoFar the list keeping any visited connection
	 * @param source startNode
	 * @param target endNode
	 * @return the list of connections indicating the path, which may be null, 
	 * if no path is possible
	 */
	private List<IConnection> getSubPath(List<IConnection> goneSoFar, INode source, INode target, boolean checkForCapacity)
	{
		if (source.getOutboundingConnections() != null) { 
			for (IConnection connection: source.getOutboundingConnections())
			{	
				// checks if the connection is still valid or if a phantomConnection consumes its free capacity
				if (getFreeCapacityOnConnection(connection) > 0 || !checkForCapacity) { 
					// target found
					if (connection.getTargetNode().equals(target))
					{
						goneSoFar.add(connection);
						return goneSoFar;
					}
					else
					{
						// if next node has not been visited so far
						boolean visited = false;
						for (IConnection oldConnection: goneSoFar) {
							if (oldConnection.getSourceNode().equals(connection.getTargetNode())) {
								visited = true;
								break;
							}
						}
						if (!visited)
						{
							goneSoFar.add(connection);
							List<IConnection> connections = getSubPath(goneSoFar, connection.getTargetNode(), target, checkForCapacity);
							if (connections != null) 
								return connections;
							// The next node had no connection, so we had to go back
							goneSoFar.remove(connection);
						}		
						// No return here!!! The Connection has to check all its outgoing connections...
					}
				}
			}
		}
		// if there are no outboundingConnections
		return null;
	}
	
	/**
	 * This method is used to find out the direct connection between two nodes.
	 * If no such direct connection exists, it returns null.
	 * 
	 * @param source - source node
	 * @param target - target node
	 * @return the direct connection, may be null
	 */
	public IConnection getSinglePath(INode source, INode target)
	{
		for (IConnection connection: connections)
			if (connection.getSourceNode() == source &&
				connection.getTargetNode() == target)
				return connection;
		return null;
	}
	
	/**
	 * This method returns all marked nodes. 
	 * 
	 * @return a list of all nodes, which have been marked so far.
	 */
	protected List<INode> getMarkedNodes() {
		
		return visitedSoFar;
	}
	
	/**
	 * @see ICore#initialize(List, List)
	 */
	@Override
	public void initialize(List<INode> nodes, List<IConnection> connections) throws InvalidDataException {
		this.nodes = nodes;
		this.connections = connections;
		
		if (nodes == null || connections == null)
			throw new InvalidDataException("Nodes and Connections may not be null");
		
		this.compensationNode = addCompensationNode();
			
		for (INode node: nodes)
			node.setOriginalCapacity(node.getCapacity());
			
		this.initialized = true;
	}
	
	/**
	 * This method will try to create an initial balance to prepare the kilteralgorithm.
	 * After having set up this initial solution, it will notify all listeners of the 
	 * first iteration being completed.
	 * 
	 * @throws NotInitializedException - is thrown, if {@link #initialize(List, List)} has not been called
	 * @throws InvalidDataException - is thrown, if the underlying data is incorrect.
	 */
	protected void prepareForKilter() throws NotInitializedException, InvalidDataException {

		boolean finished = false;
		
		while(!finished)
		{
			finished = true;
			for (INode node: nodes)
			{
				if (node.getCapacity() > 0)
				{
					finished = false;
					
					List<IConnection> negativeChildWay = getNegativeChild(node);

					if (negativeChildWay == null)
						throw new InvalidDataException("The node \""+ node.getName() +"\" could not be balanced");
					
					INode negativeChild = negativeChildWay.get(negativeChildWay.size()-1).getTargetNode();
					int negativeChildCapacity = negativeChild.getCapacity();	
					int difference = node.getCapacity() + negativeChildCapacity;
					
					if (difference < 0)
					{
						negativeChild.addCapacity(node.getCapacity());
						
						for (IConnection connection: negativeChildWay)
							connection.addLoad(node.getCapacity());
						
						node.setCapacity(0);
					}
					else
					{
						node.addCapacity(negativeChildCapacity);
						
						for (IConnection connection: negativeChildWay)
							connection.addLoad(Math.abs(negativeChildCapacity));
						
						negativeChild.setCapacity(0);
					}
					fireIterationCompleted(this.nodes, this.connections);
				}
			}
		}
		
//		for (IConnection connection: this.connections) {
//			connection.setLoad(0);
//		}
//		
//		connections.get(0).setLoad(20); // A -> B
//		connections.get(1).setLoad(0); // B -> C
//		connections.get(2).setLoad(20); // A -> D
//		connections.get(3).setLoad(0); // D -> B
//		connections.get(4).setLoad(30); // D -> C
//		connections.get(5).setLoad(0); // C -> A
	
		for (INode node: nodes)
			if (node.getCapacity() != 0)
				throw new InvalidDataException("The node \"{"+ node.getName() +"}\" could not be balanced");
	}
	
	/**
	 * This method contains the main computation algorithms. It tries to balance the nodes, 
	 * calculates decreased costs and the connection's states. 
	 * After having completed a certain iteration, this method will notify all listeners
	 * of the completed iteration.
	 * 
	 * @throws InfiniteLoopException - is thrown, if the computation results in an infite loop
	 * @throws InvalidDataException - is thrown, if the underlying data is incorrect
	 */
	protected void outOfKilter() throws InfiniteLoopException, InvalidDataException
	{
		boolean finished = false;
		
		for (IConnection conn: connections)
		{
			conn.calculateDecreasedCosts();
			conn.calculateState();
		}
		
		while (!finished)
		{
			finished = true;
			
			for (IConnection connection: connections)
			{
				
				if (connection.getState()<0)
				{
					finished = false;
//					System.out.println(connection);
					mark(connection);
					for (IConnection conn: connections)
					{
						conn.calculateDecreasedCosts();
						conn.calculateState();
					}
					fireIterationCompleted(this.nodes, this.connections);
					break;
					
				}
			}
		}
	}
	
	/**
	 * This method is used to track the marked nodes. Therefore it will also compute the
	 * connection's states, and try to find a semicyle by calling {@link #getSemiCylce(List, INode, INode)}.
	 * 
	 * 
	 * @param connection - the connection to be evaluated
	 * @throws InfiniteLoopException - is thrown, if the computation results in an infite loop
	 * @throws InvalidDataException - is thrown, if the underlying data is incorrect
	 */
	protected void mark(IConnection connection) throws InfiniteLoopException, InvalidDataException {
		int kilterDelta = 0;
		INode sourceNode = null;
		INode targetNode = null;
		
		/*
		 * Here we check the state of the connection to mark the nodes
		 * and start the getSemiCycle() method correctly;
		 */
		switch (connection.getState())
		{
			case -1:
			{
				sourceNode = connection.getTargetNode();
				targetNode = connection.getSourceNode();

				kilterDelta = connection.getMinimumCapacity() - connection.getLoad();
				break;
			}
			case -3:
			case -5:
			{
				kilterDelta = connection.getMaximumCapacity() - connection.getLoad();
				
				sourceNode = connection.getTargetNode();
				targetNode = connection.getSourceNode();				
				break;				
			}
			case -2:
			case -6:
			{
				kilterDelta = connection.getLoad() - connection.getMinimumCapacity();
				
				sourceNode = connection.getSourceNode();
				targetNode = connection.getTargetNode();
				break;
			}
			case -4:
			{
				kilterDelta = connection.getLoad() - connection.getMaximumCapacity();	
				
				sourceNode = connection.getSourceNode();
				targetNode = connection.getTargetNode();
				break;
			}
		}
		
		List<INode> semiCycle = getSemiCylce(new Vector<INode>(), sourceNode, targetNode);
		
		IConnection path = null;
		/*
		 *  If we found a semi cycle we can look for the smallest possible value that can be 
		 *  transferred by it (kilterDelta). Then we push this value over the connections.
		 */
		if (semiCycle != null)
		{
			lastCapacities = null;
			currentLoopLevel = 0;
			for (int i = 0; i < semiCycle.size()-1; i++)
			{
				path = getSinglePath(semiCycle.get(i), semiCycle.get(i+1));
				// If the nodes i and i+1 are connected by a Connection from node i to i+1
				if (path != null)
				{
					if (path.getDecreasedCost() > 0 &&
						path.getLoad() < path.getMinimumCapacity())
						kilterDelta = Math.min(kilterDelta, path.getMinimumCapacity() - path.getLoad());
					if (path.getDecreasedCost() <= 0 &&
						path.getLoad() < path.getMaximumCapacity())
						kilterDelta = Math.min(kilterDelta, path.getMaximumCapacity() - path.getLoad());
				} 
				else // If the nodes i and i+1 are connected by a Connection from node i+1 to i
				{
					path = getSinglePath(semiCycle.get(i+1), semiCycle.get(i));
					if (path != null)
					{
						if (path.getDecreasedCost() >= 0 &&
							path.getLoad() > path.getMinimumCapacity())
							kilterDelta = Math.min(kilterDelta, path.getLoad() - path.getMinimumCapacity());
						if (path.getDecreasedCost() < 0 &&
							path.getLoad() > path.getMaximumCapacity())
							kilterDelta = Math.min(kilterDelta, path.getLoad() - path.getMaximumCapacity());
					}
				}
			}

			for (int i = 0; i < semiCycle.size()-1; i++)
			{
				path = getSinglePath(semiCycle.get(i), semiCycle.get(i+1));
				
				// If the nodes i and i+1 are connected by a Connection from node i to i+1
				if (path != null)
					path.addLoad(kilterDelta); // We have to add the load, as the connection follows the "flow" of the semi cycle
				else // If the nodes i and i+1 are connected by a Connection from node i+1 to i
				{	
					path = getSinglePath(semiCycle.get(i+1), semiCycle.get(i));
					
					if (path != null)
						path.addLoad(-kilterDelta); // We have to substract the load, as the connection is vice versa to the "flow" of the semi cycle
				}			
			}
		}
		/*
		 * If we've found no semi cycle we have to change the (original) capacity of the nodes
		 * by finding the connection with the lowest decreased costs and adding it (the decreased costs)
		 * to all unmarked nodes.
		 */
		else
		{
			List<INode> markedNodes = getMarkedNodes();
			IConnection n1 = null;
			IConnection n2 = null;
			int n = 0;
			
			/*
			 * Here we are checking all connections from marked nodes to unmarked nodes.
			 * If we've found a connection, we compare its decreased costs to the decreased costs
			 * of the connection with the currently smallest decreased costs (n1). If n1 is still 
			 * null, we set the current connection to n1.
			 */
			for (INode node: markedNodes)			
				if (node.getOutboundingConnections() != null)
					for(IConnection conn: node.getOutboundingConnections())
						if (!markedNodes.contains(conn.getTargetNode()))
							if (conn.getDecreasedCost() > 0 &&
								conn.getLoad() <= conn.getMaximumCapacity())
								if (n1 == null)
									n1 = conn;
								else 
									if (conn.getDecreasedCost() < n1.getDecreasedCost())
										n1 = conn;
			
			/*
			 * Here we are checking all connections from unmarked nodes to marked nodes.
			 * If we've found a connection we compare its decreased costs to the decreased costs
			 * of the connection with the currently smallest decreased costs (n2). If n2 is still 
			 * null, we set the current connection to n2.
			 */
			for (INode node: markedNodes)		
				if (node.getInboundingConnections() != null)
					for(IConnection conn: node.getInboundingConnections())
						if (!markedNodes.contains(conn.getSourceNode()))
							if (conn.getDecreasedCost() < 0 &&
								conn.getLoad() >= conn.getMinimumCapacity())
								if (n2 == null)
									n2 = conn;
								else
									if (conn.getDecreasedCost()*-1 < n2.getDecreasedCost()*-1)
										n2 = conn;

			/*
			 *  Here we check which decreased cost is the smaller one 
			 *  (the one from n1 or the one from n2) and save the resulting 
			 *  decreased cost in n.
			 */
			if (n1 != null)
			{
				if (n2 != null)
					n = Math.min(n1.getDecreasedCost(), n2.getDecreasedCost()*-1);
				else
					n = n1.getDecreasedCost();
			}
			else
			{
				if (n2 != null)
					n = n2.getDecreasedCost() * -1;
				else // This should never happen, if it does the algorithm failed...
					throw new InvalidDataException("No valid circulation flow!");
			}
		
			// Here we add the computed smallest decreased cost n to all unmarked nodes.
			boolean noChange = true; // used to determine if no node has been changed 
									 // correctly according to the rules of the algorithm
			
			int checked = 0; // shows how many nodes have been checked
			for (INode node: nodes)
				if (!markedNodes.contains(node)) {
					if (lastCapacities != null) { // at least second iteration without semi cycle
						if (lastCapacities.get(node) != null) { // node was changed in last iteration
							checked++;
							if (((Integer)lastCapacities.get(node)).intValue() != -n) // node was NOT changed by the same (negative) amount in the last loop
									noChange = false;
						} else // node was not changed in the last iteration
							noChange = false;
						
					} else // first iteration or semi cycle
						noChange = false;
					
					node.addOriginalCapacity(n);
				}
			
			// checks if no change was found and if 
			if (noChange && checked == lastCapacities.size()) {
				currentLoopLevel++;
				if (currentLoopLevel >= maxLoopLevel) throw new InfiniteLoopException("Current iteration with difference " + n + " results in an infinite loop(loopLevel=" + currentLoopLevel + ")!");
			} else 
				currentLoopLevel = 0;
			
			
			lastCapacities = new HashMap<INode, Integer>();
			
			for (INode node: nodes)
				if (!markedNodes.contains(node)) 
					lastCapacities.put(node, n);
		}
	}
	
	/**
	 * @see de.uv.kilter.core.ICore#removeAllIterationCompletedListeners()
	 */
	@Override
	public void removeAllIterationCompletedListeners() {
		listeners.clear();
	}
	
	/**
	 * @see de.uv.kilter.core.ICore#removeIterationCompletedListener(de.uv.kilter.core.IIterationCompletedListener)
	 */
	@Override
	public void removeIterationCompletedListener(
			IIterationCompletedListener listener) {
		listeners.remove(listener);
	}
	
	/**
	 * This method calls @link {@link INode#removeAllInboundingPhantomConnections()} and 
	 * {@link INode#removeAllOutboundingPhantomConnections()} for all registered nodes.
	 */
	protected void removePhantomConnectionsFromAllNodes() {
		if (this.nodes != null) {
			for (INode node: this.nodes) {
				node.removeAllInboundingPhantomConnections();
				node.removeAllOutboundingPhantomConnections();
			}
		}
	}

}
